#include<bits/stdc++.h>
const int N = 100;

// 二分查找
void binary_find(const std::vector<int>& a, int target)
{
    int l = -1, r = a.size();

    auto check = []() -> bool
    {
        // isblue function
        return true;
    };

    while(l + 1 != r)
    {
        int mid = (l + r) >> 1;
        if(check) l = mid;
        else r = mid;
    }
}

// 判定质数
bool is_prime(int n)
{
    if(n < 2) return false;
    for(int i = 2; i <= n / i; i ++)
    {
        if(n % i == 0) return false;
    }
    return true;
}

// 筛选 1 - n之间的所有素数
// 埃氏筛法
void get_prime(int n)
{
    std::vector<int> primes;
    bool visited[N];
    memset(visited, false, sizeof visited);
    for(int i = 2; i <= n; i ++)
    {
        if(visited[i]) continue;
        primes.push_back(i);
        for(int j = i * 2; j <= n; j += i)
            visited[j] = true;
    }
}

// 分解质因数
std::vector<std::pair<int, int>> divide(int x)
{
    // 底数 质数 组合
    std::vector<std::pair<int, int>> factors;
    for(int i = 2; i <= x / i; i ++)
    {
        // i 为 底数
        if(x % i == 0)
        {
            int cnt = 0;
            while(x % i == 0)
            {
                x /= i;
                cnt ++;
            }
            factors.push_back({i, cnt});
        }
    }
    if(x > 1) factors.push_back({x, 1});
    return factors;
}

// 快速排序
void quick_sort(std::vector<int>& a)
{
    std::function<void(int, int)> recursive_quick_sort = 
    [&](int l, int r) -> void
    {
        if(l >= r) return;
        int x = a[l + r >> 1], i = l - 1, j = r + 1;
        while(i < j)
        {
            while(a[++i] < x);
            while(a[--j] > x);
            if(i < j) std::swap(a[i], a[j]);
        }
        recursive_quick_sort(l, j);
        recursive_quick_sort(j + 1, r);
    };

    recursive_quick_sort(0, a.size() - 1);
}

// 前缀和
std::vector<int> prefix_sum_one_dimension(std::vector<int>& a)
{
    std::vector<int> prefix_sum(a.size() + 1);
    prefix_sum[0] = 0;
    for(int i = 1; i <= a.size(); i ++)
    {
        prefix_sum[i] = prefix_sum[i - 1] + a[i - 1];
    }
    return prefix_sum;
}

// 二维前缀和
std::vector<std::vector<int>> prefix_sum_two_dimension(
    const std::vector<std::vector<int>>& g)
{
    std::vector<std::vector<int>> prefix_sum(
        g.size() + 1, std::vector<int>(g[0].size() + 1, 0));

    for(int i = 1; i <= g.size(); i ++)
    {
        for(int j = 1; j <= g[0].size(); j ++)
        {
            prefix_sum[i][j] = prefix_sum[i - 1][j] + prefix_sum[i][j - 1]
                                - prefix_sum[i - 1][j - 1] + g[i][j];
        }
    }
    
    // 给定两个坐标 (x1, y1) (x2, y2) 求其中所有元素的和
    //             (x2, y1) (x1, y2)
    // prefix_sum[x2][y2] - prefix_sum[x2][y1 - 1] - preifix_sum[x1 - 1][y2] + prefix_sum[x1 - 1][y1 - 1]
    return prefix_sum;
}

// 实现 Trie
class Trie
{
    static constexpr int N = 1000;
    int son[N][26], cnt[N], idx;
    
    void insert(std::string str)
    {
        int p = 0;
        for(int i = 0; i < str.size(); i ++)
        {
            int u = str[i] - 'a';
            if(!son[p][u]) son[p][u] = ++idx;
            p = son[p][u];
        }
        cnt[p] ++;
    }

    int query(std::string str)
    {
        int p = 0;
        for(int i = 0; i < str.size(); i ++)
        {
            int u = str[i] - 'a';
            if(!son[p][u]) return 0;
            p = son[p][u];
        }
        return cnt[p];
    }
};

// 并查集类
class UnionFind
{
    static constexpr int N = 1000;
    int father[N];

    public:

    void init()
    {
        for(int i = 1; i <= N; i ++) father[i] = i;
    }

    int find(int x)
    {
        while(x != father[x]) x = father[x];
        return x;
    }

    void merge(int a, int b)
    {
        int faA = find(a);
        int faB = find(b);
        if(faA != faB) father[faA] = faB;
    }
};

class Graph_Traverse
{
    std::unordered_map<int, std::vector<int>> g;

    void dfs()
    {
        std::unordered_set<int> visited;
        std::function<void(int)> recursize_dfs = [&](int idx) -> void
        {
            // 全部结点都被访问过时return
            if(visited.count(idx)) return;
            
            for(auto& node : g[idx])
            {
                if(!visited.count(node))
                {
                    visited.insert(node);
                    recursize_dfs(node);
                }
            }
        };
    }

    void bfs()
    {
        std::deque<int> q;
        std::unordered_set<int> visited;
        // 每个被访问结点的前驱
        std::vector<int> pre;
        q.push_back(1);
        pre[1] = -1;
        while (!q.empty())
        {
            int tp = q.front();
            q.pop_front();
            if(visited.count(tp)) continue;
            visited.insert(tp);
            for(auto& node : g[tp])
            {
                if(!visited.count(node)) 
                {
                    q.push_back(node);
                    pre[node] = tp;
                }
            }
        }
    }
};

class dijsktra
{
    std::unordered_map<int, std::vector<std::pair<int, int>>> g;
    int dist[N];

    void Dijsktra(int start, int end)
    {
        int dist[N];
        memset(dist, 0x3f, sizeof dist);

        std::unordered_set<int> visited;
        std::vector<int> pre(N, -1);

        std::priority_queue<
        std::pair<int, int>,
        std::vector<std::pair<int, int>>,
        std::greater<std::pair<int, int>>
        > q;

        q.push({0, start});
        dist[start] = 0;
        pre[start] = -1;

        while (!q.empty())
        {
            auto tp = q.top();
            q.pop();
            int distant = tp.first;
            int index = tp.second;
            if(visited.count(index)) continue;;
            visited.insert(index);
            for(auto& node : g[index])
            {
                if(dist[node.first] > distant + node.second)
                {
                    dist[node.first] = distant + node.second;
                    pre[node.first] = index;
                    q.push({dist[node.first], node.first});
                }
            }
        }
    }
};

class Floyd
{
    int dist[N][N];

    void floyd()
    {
        for(int k = 1; k <= N; k ++)
        {
            for(int i = 1; i <= N; i ++)
            {
                for(int j = 1; j <= N; j ++)
                {
                    dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
};

class MST
{
    // u,v,w
    std::unordered_map<int, std::vector<std::pair<int, int>>> g;
    int node_size = g.size();

    int prim()
    {
        std::vector<int> dist(node_size, 0x3f3f3f3f);
        std::unordered_set<int> visited;
        int ans = 0;

        for(int i = 0; i < node_size; i ++)
        {
            int t = -1;
            for(int j =1; j <= node_size; j ++)
            {
                if(!visited.count(j) && (t == -1 || dist[j] < dist[t]))
                {
                    t = j;
                } 
            }
            // 不可达
            if(i && dist[t] == 0x3f3f3f3f) return -1;
            if(i) ans += dist[t];
            // 更新所有的dist
            for(auto& node : g[t])
            {
                if(!visited.count(node.first) && dist[node.first] > node.second)
                {
                    dist[node.first] = node.second;
                }
            }
            // 标记为访问过
            visited.insert(t);
        }
        return ans;
    }

    int kruskal()
    {
        // w, u, v
        using PIII = std::pair<int, std::pair<int, int>>;
        // 处理所有的边集合
        std::vector<PIII> edges;

        for(auto& node : g)
        {
            for(auto& edge : node.second)
            {
                edges.push_back({edge.second, {node.first, edge.first}});
            }
        }

        std::sort(edges.begin(), edges.end(), [](PIII a, PIII b)
        -> bool
        {
            // 从小到大排序
            return a.first > b.first;
        });

        UnionFind uf;
        uf.init();

        int ans = 0;
        for(auto& edge : edges)
        {
            int u = edge.second.first;
            int v = edge.second.second;
            int w = edge.first;
            
            if(uf.find(u) != uf.find(v))
            {
                ans += w;
                uf.merge(u, v);
            }
        }
        
        return ans;
    }
};

class Topu_sort
{
    std::unordered_map<int, std::vector<int>> g;
    std::unordered_map<int, int> in_degree;
    std::vector<int> ans;
    int node_size = g.size();

    void topu_sort()
    {
        std::deque<int> q;

        for(int i = 0; i < node_size; i ++)
        {
            if(in_degree[i] == 0) 
            {
                ans.push_back(i);
                q.push_back(i);
            }
        }

        while(!q.empty())
        {
            int tp = q.front();
            q.pop_front();

            for(auto& node : g[tp])
            {
                in_degree[node] --;
                if(in_degree[node] == 0)
                {
                    ans.push_back(node);
                    q.push_back(node);
                }
            }
        }
    }
};

class BackPack
{
    void _01backpack()
    {
        int n, m;
        int dp[N][N];
        int v[N], w[N];

        for(int i = 1; i <= n; i ++)
        {
            for(int j = 0; j <= m; j ++)
            {
                if(j >= w[i])
                    dp[i][j] = std::max(
                        dp[i - 1][j],
                        dp[i - 1][j - w[i]] + v[i]);
            }
        }

        int dpp[N];
        for(int i = 1; i <= n; i ++)
            for(int j = m; j >= 0; j --)
            {
                if(j >= w[i])
                    dpp[j] = std::max(
                        dpp[j],
                        dpp[j - w[i]] + v[i]
                    );
            }
    }

    void completebackpack()
    {
        int n, m;
        int dp[N][N];
        int v[N], w[N];

        for(int i = 1; i <= n; i ++)
            for(int j = 0; j <= m; j ++)
            {
                if(j >= w[i])
                    dp[i][j] = std::max(
                        dp[i - 1][j],
                        dp[i][j - w[i]] + v[i]
                    );
            }

        int dpp[N];
        for(int i = 1; i <= n; i ++)
            for(int j = 0; j <= m; j ++)
            {
                if(j >= w[i])
                    dpp[j] = std::max(
                        dpp[j],
                        dpp[j - w[i]] + v[i]
                    );
            }
    }

    void multiplebackpack()
    {
        int n, m;
        int dp[N];

        // value, weight, number
        int v, w, s;
        // see-as complete backpack
        for(int i = 1; i <= n; i ++)
        {
            std::cin >> v >> w >> s;
            for(int j = m; j >= 0; j --)
            {
                for(int k = 0; k <= s; k ++)
                {
                    if(j >= k * w)
                        dp[j] = std::max(
                            dp[j],
                            dp[j - k * w] + k *v);
                }
            }
        }

        // 拆开
        std::vector<std::pair<int, int>> goods;
        for(int i = 1; i <= n; i ++)
        {
            std::cin >> v >> w >> s;
            for(int k = 1; k <= s; k *= 2)
            {

                goods.push_back({w * k, v * k});
                s -= k;
            }
            if(s > 0) goods.push_back({w * s, v * s});
        }

        for(auto& good : goods)
        {
            for(int j = m; j >= 0; j --)
            {
                if(j >= good.first)
                    dp[j] = std::max(
                        dp[j],
                        dp[j - good.first] + good.second
                    );
            }
        }
    }

    void groupbackpack()
    {
        /*
        有 `N` 组物品和一个容量是 `V` 的背包。
        每组物品有若干个，同一组内的物品最多只能选一个。
        每件物品的体积是 v_{ij}，价值是 w_{ij}，其中 `i` 是组号，`j` 是组内编号。
        */
        int dp[N];
        int n, m;
        int v[N], w[N];
        for(int i = 1; i <= n; i ++)
        {
            // number of items
            int s;
            std::cin >> s;
            for(int k = 1; k <= s; k ++)
            {
                std::cin >> v[k] >> w[k];
            }

            for(int j = m; j >= 0; j --)
            {
                for(int k = 1; k <= s; k ++)
                {
                    if(j >= v[k])
                        dp[j] = std::max(
                            dp[j],
                            dp[j - v[k]] + w[k]
                        );
                }
            }
        }
    }
};  

class DP_Compression_State
{
    // 判断 x 之间是否具有相邻的0或1，只有0101这样满足条件
   std::function<bool(int)> function_row_judge = [](int x) -> bool
    {
        return (x & (x << 1)) == 0;
    };

    // 判断 a 和 b 在同一列是否具有相邻的0或1
    std::function<bool(int,int)> function_col_judge = [](int a, int b) -> bool
    {
        return ((a & b) == 0);
    };
};